package swordoffer.offer53_2;

public class MissingNumber {
    public int missingNumber(int[] nums) {
        /**
         * 特殊情况判断，由于数组长度为n - 1, 而出现的数字范围为 0 --- (n - 1), 共有n个数字可以出现。
         *      当0 --- n - 1的所有数字都出现时，缺失的数字就是n
         */
        int n = nums.length;
        if(nums[n - 1] == n - 1){
            return n;
        }
        int left = 0;
        int right = n - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == mid){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    }
}
